#include <stdio.h>/*该文件包含pringtf()等函数*/
#include <stdlib.h>/*该文件包含exit()等函数*/
#include <malloc.h>/*该文件包含malloc()等函数*/


#define STACK_MAX_SIZE 100 // 栈最多支持存放100个数据元素

#define bool int

typedef struct stack {
    int * base;
    int * top;
    int number_of_elements; // 栈内实际数据元素个数
} * Stack;




bool is_operator(char symbol){

    if (symbol == '*') {
        return 1 ;
    }
    else if (symbol == '-')  {return 1;}
    else if (symbol == '+')  return 1;
    else if (symbol == '/')  return 1;
    else if (symbol == '(')  return 1;
    else if (symbol == ')')  return 1;
    else if (symbol == '#')  return 1;
    else return 0;
//    switch (symbol) {
//        case '*':  return 1 ;break;
//        case '-':  return 1 ;break;
//        case '+':  return 1 ;break;
//        case '/':  return 1 ;break;
//        case '(':  return 1 ;break;
//        case ')':  return 1 ;break;
//        case '#':  return 1 ;break;
//
//
//
//    }

}


// 判断刚扫描到的symbol是否操作数。如果symbol是操作数，返回1，否则返回0。
//操作数 0,1,2,3,4,5,6,7,8,9
bool is_operand(char symbol){

    if (symbol == '0')  return 1;
    else if (symbol == '1')  return 1;
    else if (symbol == '2')  return 1;
    else if (symbol == '3')  return 1;
    else if (symbol == '4')  return 1;
    else if (symbol == '5')  return 1;
    else if (symbol == '6')  return 1;
    else if (symbol == '7')  return 1;
    else if (symbol == '8')  return 1;
    else if(symbol == '9')  return 1;

    else return 0;



}


// 初始化名为s的栈，初始化成功，返回0，否则返回1。
int init_stack(Stack * s) {
    (*s) = malloc(sizeof (struct stack));
    (*s) -> base  = malloc(STACK_MAX_SIZE * sizeof(int));
    if(!(*s) -> base) return 1;

    (*s) -> top = (*s)->base;
    (*s) -> number_of_elements = STACK_MAX_SIZE;
    return 0;
}

// 入栈。返回值表示是否压栈成功：0，成功；1，不成功。
int push(Stack s, char operator_or_operand){
    if(s -> top - s->base == s->number_of_elements) return 1;
    *(s->top) = operator_or_operand;
    s -> top = s->top +1;
    return 0;
}

// 出栈。返回值表示是否出栈成功：0，成功，1，不成功。
int pop(Stack s, char *p_operator_or_operand){
    if(s->top == s->base) return 1;

    *p_operator_or_operand =  *--(s->top);
    return 0;
}

// 只返回栈顶元素，通过result变量返回栈顶元素的值。函数返回值用于表示执行状态：0，成功；1，不成功。
int get_top(Stack s, char * result) {
    if(s->top == s->base) return 1;
    *result  = *(s->top - 1)  ;
//    printf("顶元素是：%c\n",result);
    return 0;
}

// 处理操作符。operator_on_stack_top表示操作符栈栈顶的操作符，just_scanned_operator表示从表达式里刚刚读取的操作符。返回值表示优先级：
//  -1, operator_on_stack_top 的优先级低于 just_scanned_operator；
//  0，operator_on_stack_top 的优先级等于 just_scanned_operator；
//  1，operator_on_stack_top 的优先级高于 just_scanned_operator。
int compare_operators(char operator_on_stack_top, 
                      char just_scanned_operator) {
    char a[][7]={
            {'>','>','<','<','<','>','>'},
            {'>','>','<','<','<','>','>'},
            {'>','>','>','>','<','>','>'},
            {'>','>','>','>','<','>','>'},
            {'<','<','<','<','<','=',' '},
            {'>','>','>','>',' ','>','>'},
            {'<','<','<','<','<',' ','='}
    };



    if(is_operator(just_scanned_operator) && is_operator(operator_on_stack_top)) {
        int i, j;

        if (operator_on_stack_top == '+') i = 0;
        if (operator_on_stack_top == '-') i = 1;
        if (operator_on_stack_top == '*') i = 2;
        if (operator_on_stack_top == '/') i = 3;
        if (operator_on_stack_top == '(') i = 4;
        if (operator_on_stack_top == ')') i = 5;
        if (operator_on_stack_top == '#') i = 6;


        if (just_scanned_operator == '+') j = 0;
        if (just_scanned_operator == '-') j = 1;
        if (just_scanned_operator == '*') j = 2;
        if (just_scanned_operator == '/') j = 3;
        if (just_scanned_operator == '(') j = 4;
        if (just_scanned_operator == ')') j = 5;
        if (just_scanned_operator == '#') j = 1;


        switch (a[i][j]) {
            case '>':
                return 1;
            case '<':
                return -1;
            case '=':
                return 0;

        }
    }
}

// 用于简单计算+，-，*，/，operator表示操作符，left_operand表示左操作数，right_operand表示右操作数，结果通过result返回。函数返回值表示计算状态：0，计算成功；1，不成功。
int caculate(char operator, char left_operand, char right_operand, int * result) {
    int i, j ;

    if (left_operand == '0') i = 0;
    if (left_operand == '1') i = 1;
    if (left_operand == '2') i = 2;
    if (left_operand == '3') i = 3;
    if (left_operand == '4') i = 4;
    if (left_operand == '5') i = 5;
    if (left_operand == '6') i = 6;
    if (left_operand == '7') i = 7;
    if (left_operand == '8') i = 8;
    if (left_operand == '9') i = 9;

    if (right_operand == '0') j = 0;
    if (right_operand == '1') j = 1;
    if (right_operand == '2') j = 2;
    if (right_operand == '3') j = 3;
    if (right_operand == '4') j = 4;
    if (right_operand == '5') j = 5;
    if (right_operand == '6') j = 6;
    if (right_operand == '7') j = 7;
    if (right_operand == '8') j = 8;
    if (right_operand == '9') j = 9;

    if (operator == '+') *result = i + j;
    if (operator == '-') *result = i - j;
    if (operator == '*') *result = i * j;
    if (operator == '/') *result = i / j;

    return *result;
}

// 最主要的函数，用于计算表达式的值，比如#3*(2+6)/4#。返回值表示求值状态：0，合法表达式，成功求值；1，表达式不合法。result变量用于返回计算结果。
int evaluate(char * expression, int * result) {
    struct stack *s1;
    struct stack *s2;//s1是用于操作符的栈，s2的是用于字符数字的栈

    char left_operand;
    char right_operand;

    init_stack(&s1);
    init_stack(&s2);
    push(s1, '#');
    char Top;
     int i = 1;

    char d = expression[i];
    while ( (d != '#' ||   Top != '#') ) {



       d = expression[i];

        if (is_operand(d)) {  //操作数字栈
            push(s2,d);
            i++;



        }

        if(is_operator(d)){  //判断是否为操作符，若是则比较操作符的优先级

            char c;
            get_top(s1, &c);//取头元素


            if (compare_operators(c,d) == -1) {

                push(s1, d);
                i++;


            }
            if (compare_operators(c,d) == 1) {

                int R;//计算结果
                char A;
                pop(s2, &right_operand);
                pop(s1,&c);
                pop(s2, &left_operand);
                caculate(c, left_operand, right_operand, &R);
                A = R + 48;
                push(s2,A);






            }

            if ((compare_operators(c, d) == 0 && (c == '(')) && (d == ')')) {
                pop(s1, &c);
                i++;

            }
        }

        get_top(s1,&Top) ;

    }


    get_top(s2,&Top) ;
    *result = Top - 48;
    return *result;

}

// 编写你们组自己使用的测试代码
int main(int argc, char * argv[]) {
   char *a = "#2*(2+1)#";
    int t;
    evaluate(a,&t);
    printf("%d\n",t);
  return 0;
}